1. Field of the Invention
This invention relates to a vector generator for drawing lines in a computer graphics system having parallel rasterizers, as well as to a triangle processor containing such a line generator.
2. Description of the Related Art
Line drawing is a basic task in most computer graphics systems, since line segments are the basic elements of the objects (lines, polylines, polygons, etc.) that are displayed on a screen. Generally, "primitives" consisting of or containing line segments are stored in the form of the coordinates of the line endpoints. On the other hand, the actual image that is displayed consists of a two-dimensional (2-D) array of "pixels", each of which in the simplest case may be given either a foreground or a background shading value. In order to display a line segment stored in coordinate form, the line segment must first be "rasterized", or converted to a suitable pattern of pixels approximating the true line.
The most common line-drawing procedures in use today are Bresenham's procedure, described in J. Bresenham, "Algorithm for Computer Control of a Digital Plotter", IBM Systems Journal 4(1), 1965, 25-30, and the digital differential analyzer (DDA) procedure described in J. Foley et al., Computer Graphics: Principles and Practice, Addison-Wesley, 1990, 73-74. Bresenham's procedure generates lines using integer arithmetic with no divide operations; it also accumulates no error during iteration. The DDA procedure requires a divide operation to calculate the slope of the line and the use of several fraction bits to minimize accumulation error. The divide operation and the additional fraction bits can add significant cost to a hardware implementation of DDA versus Bresenham's procedure.
Despite the clear disadvantage of the DDA procedure, recent line-drawing hardware, described in A. Barkans, "High Speed High Quality Antialiased Vector Generation", Proceedings of SIGGRAPH'90 (Dallas, Tex., Aug. 6-10, 1990), in Computer Graphics 24, 4 (August 1990), pp. 319-326, and K. Akeley et al., "High-Performance Polygon Rendering", Proceedings of SIGGRAPH'88 (Atlanta, Ga., Aug. 1-5, 1988), in Computer Graphics 22, 4 (August 1988), pp. 239-246, has used DDA because it directly supports subpixel addressing. The Apollo DN10000 described in O. Lathrop et al., "Accurate Rendering by Subpixel Addressing", IEEE Computer Graphics and Application 10, 5 (September 1990), pp. 45-53, implements a Bresenham-type procedure for line-drawing iteration that supports subpixel precision, but it requires floating-point initialization of the iteration hardware that includes divide and round operations. What is desired is a procedure that provides subpixel precision, yet requires only integer arithmetic.
To support high-performance rendering into a frame buffer most workstations, such as those disclosed by Akeley et al. (1988) and Barkans (1990) in the publications identified above, utilize a parallel processor rendering architecture. Each processor in this array controls a fraction of the screen memory and all processors are interleaved throughout the screen. With the increasing densities available with today's technology it is possible to have each processor accept higher order primitives like lines and triangles rather then single pixels, thus reducing the bandwidth requirements for input to the processor array. However, most current line and triangle iteration procedures work in single-pixel steps requiring a processor to process pixels that it does not own. It is desirable to have a procedure that allows a processor to skip over pixels that it does not own.
W. Wright, "Parallelization of Bresenham's Line and Circle Algorithms", IEEE Computer Graphics and Application, 10(5), (September 1990), 60-67, discloses a parallel Bresenham procedure, but it assumes shared memory between processors and that each processor can have control of on arbitrary pixel on the screen. Sharing frame buffer space among raster engines would result in much higher bandwidth requirements going into the frame buffer, therefore in current implementations the pixels for which a processor has control is fixed. Barkans (1990) describes a parallel procedure implemented for four processors, but uses a DDA procedure with its attendant disadvantages.